//leetcode_33:搜索旋转排序数组
//给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。输入：nums = [4,5,6,7,0,1,2], target = 0
//        输出：4
//        示例2：
//        输入：nums = [4,5,6,7,0,1,2], target = 3
//        输出：-1
//        示例 3：
//        输入：nums = [1], target = 0
//        输出：-1
//说白了就是时间复杂度从O(n)优化为O(logn)
//数组为两个递增得子数组
public class leetcode_33 {

    //根据二分法
    public int search(int[] nums, int target) {
        int lo = 0, hi = nums.length - 1, mid = 0;
        while (lo <= hi) {
            mid = lo + (hi - lo) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            // 先根据 nums[mid] 与 nums[lo] 的关系判断 mid 是在左段还是右段
            if (nums[mid] >= nums[lo]) {
                // 再判断 target 是在 mid 的左边还是右边，从而调整左右边界 lo 和 hi
                if (target >= nums[lo] && target < nums[mid]) {
                    hi = mid - 1;
                } else {
                    lo = mid + 1;
                }
            } else {
                if (target > nums[mid] && target <= nums[hi]) {
                    lo = mid + 1;
                } else {
                    hi = mid - 1;
                }
            }
        }
        return -1;
    }
}
